package exercises.leetcode;

import exercises.newcoder.util.TreeNode;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * <a href="https://leetcode-cn.com/problems/binary-tree-postorder-traversal/">
 * 145. 二叉树的后序遍历</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定一个二叉树，返回它的 后序 遍历。
 *
 * @author or2
 * @date 2021年10月12日 时间: 13:26
 */
public class No145 {
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null)
            return Collections.emptyList();

        var stack = new LinkedList<TreeNode>();
        TreeNode prev = null;
        var res = new LinkedList<Integer>();

        stack.push(root);
        root = root.left;
        while (!stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();

            if (root.right == null || root.right == prev) {
                res.add(root.val);
                prev = root;
                root = null;
            } else {
                stack.push(root);
                root = root.right;
            }
        }

        return res;
    }
}
